/*  Copyright (c) 2010 6.172 Staff

    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
    THE SOFTWARE.
*/

/* Implements the ADT specified in bitarray.h as a packed array of bits; a
 * bitarray containing bit_sz bits will consume roughly bit_sz/8 bytes of
 * memory. */
 
#include <assert.h>
#include <stdio.h>

#include "bitarray.h"

//Mapping where bit_reverse_table[X] = char with bits that are the reverse of X, generated in Python
static char bit_reverse_table[256] = {0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240, 8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248, 4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244, 12, 140, 76, 204, 44, 172, 108, 236, 28, 156, 92, 220, 60, 188, 124, 252, 2, 130, 66, 194, 34, 162, 98, 226, 18, 146, 82, 210, 50, 178, 114, 242, 10, 138, 74, 202, 42, 170, 106, 234, 26, 154, 90, 218, 58, 186, 122, 250, 6, 134, 70, 198, 38, 166, 102, 230, 22, 150, 86, 214, 54, 182, 118, 246, 14, 142, 78, 206, 46, 174, 110, 238, 30, 158, 94, 222, 62, 190, 126, 254, 1, 129, 65, 193, 33, 161, 97, 225, 17, 145, 81, 209, 49, 177, 113, 241, 9, 137, 73, 201, 41, 169, 105, 233, 25, 153, 89, 217, 57, 185, 121, 249, 5, 133, 69, 197, 37, 165, 101, 229, 21, 149, 85, 213, 53, 181, 117, 245, 13, 141, 77, 205, 45, 173, 109, 237, 29, 157, 93, 221, 61, 189, 125, 253, 3, 131, 67, 195, 35, 163, 99, 227, 19, 147, 83, 211, 51, 179, 115, 243, 11, 139, 75, 203, 43, 171, 107, 235, 27, 155, 91, 219, 59, 187, 123, 251, 7, 135, 71, 199, 39, 167, 103, 231, 23, 151, 87, 215, 55, 183, 119, 247, 15, 143, 79, 207, 47, 175, 111, 239, 31, 159, 95, 223, 63, 191, 127, 255};


/* Internal representation of the bit array. */
struct bitarray {
  /* The number of bits represented by this bit array. Need not be divisible by 8. */
  size_t bit_sz;
  /* The underlying memory buffer that stores the bits in packed form (8 per byte). */
  char *buf;
};

bitarray_t *bitarray_new(size_t bit_sz) {
  /* Allocate an underlying buffer of ceil(bit_sz/8) bytes. */
  char *buf = calloc(1, bit_sz / 8 + ((bit_sz % 8 == 0) ? 0 : 1));
  if (buf == NULL)
    return NULL;
  bitarray_t *ret = malloc(sizeof(struct bitarray));
  if (ret == NULL) {
    free(buf);
    return NULL; }
  ret->buf = buf;
  ret->bit_sz = bit_sz;
  return ret;
}

void bitarray_free(bitarray_t *ba) {
  if (ba == NULL)
    return;
  free(ba->buf);
  ba->buf = NULL;
  free(ba);
}

size_t bitarray_get_bit_sz(bitarray_t *ba) {
  return ba->bit_sz;
}

/* Portable modulo operation that supports negative dividends. */
static size_t modulo(ssize_t n, size_t m) {
  /* See
  http://stackoverflow.com/questions/1907565/c-python-different-behaviour-of-the-modulo-operation */
  /* Mod may give different result if divisor is signed. */
  ssize_t sm = (ssize_t) m;
  assert(sm > 0);
  ssize_t ret = ((n % sm) + sm) % sm;
  assert(ret >= 0);
  return (size_t) ret;
}

static char bitmask(size_t bit_index) {
  return 1 << (bit_index % 8);
}

bool bitarray_get(bitarray_t *ba, size_t bit_index) {
  assert(bit_index < ba->bit_sz);
  return (ba->buf[bit_index / 8] & bitmask(bit_index)) ? true : false;
}

void bitarray_set(bitarray_t *ba, size_t bit_index, bool val) {
  assert(bit_index < ba->bit_sz);
  ba->buf[bit_index / 8]
      = (ba->buf[bit_index / 8] & ~bitmask(bit_index)) | (val ? bitmask(bit_index) : 0); 
}

size_t bitarray_count_flips(bitarray_t *ba, size_t bit_off, size_t bit_len) {
  assert(bit_off + bit_len <= ba->bit_sz);
  size_t i, ret = 0;
  /* Go from the first bit in the substring to the second to last one. For each bit, count another
  transition if the bit is different from the next one. Note: do "i + 1 < bit_off + bit_len" instead
  of "i < bit_off + bit_len - 1" to prevent wraparound in the case where bit_off + bit_len == 0. */
  for (i = bit_off; i + 1 < bit_off + bit_len; i++) {
    if (bitarray_get(ba, i) != bitarray_get(ba, i + 1))
      ret++;
  }
  return ret;
}

/* Rotate substring left by one bit. !NO LONGER USED! Kept to support testing of given implementation */
static void bitarray_rotate_left_one(bitarray_t *ba, size_t bit_off, size_t bit_len) {
  size_t i;
  bool first_bit = bitarray_get(ba, bit_off);
  for (i = bit_off; i + 1 < bit_off + bit_len; i++)
    bitarray_set(ba, i, bitarray_get(ba, i + 1));
  bitarray_set(ba, i, first_bit);
}

/* Rotate substring left by the specified number of bits; makes use of repeated reversals for efficient rotation. */
static void bitarray_rotate_left(bitarray_t *ba, size_t bit_off, size_t bit_len, size_t bit_amount)
{
//  OLD GIVEN IMPLEMENTATION
//  size_t i;
//  for (i = 0; i < bit_amount; i++)
//    bitarray_rotate_left_one(ba, bit_off, bit_len);

    //Use reversals as described in the project handout for efficient rotation (ab -> ba, |a| = bit_amount)
    subset_reverse(ba, bit_off, bit_amount); 			     //Reverse 'a'
    subset_reverse(ba, bit_off + bit_amount, bit_len - bit_amount); //Reverse 'b'
    subset_reverse(ba, bit_off, bit_len);                           //Reverse everything

}

void bitarray_rotate(bitarray_t *ba, size_t bit_off, size_t bit_len, ssize_t bit_right_amount) {
  assert(bit_off + bit_len <= ba->bit_sz);
  if (bit_len == 0)
    return;
  /* Convert a rotate left or right to a left rotate only, and eliminate multiple full rotations. */
  bitarray_rotate_left(ba, bit_off, bit_len, modulo(-bit_right_amount, bit_len));
}

//Extract L bits from byte b, starting at index i and leave them right-aligned
inline char bit_range_extract(size_t i, size_t L, char b) {
  assert(i < 8);
  assert(L < 9);
  assert(i + L < 9);
  return ((b << (8-i-L)) & 0xFF) >> (8-L);
}

/* Create a right-aligned bitmask (of all 1's) of the given length */
inline char one_mask(size_t length) {
  return 0xFF >> (8-length);
}

/* Reverse the specified range of bits in the bit array. ALL ranges within the bit array are valid. */
void subset_reverse(bitarray_t *ba, size_t startIndex, size_t length) {
  if (length < 1) { //A length 0 rotation does nothing; allow this input for simplified logic elsewhere
    return;
  }

  //Initialize state variables
  size_t i = startIndex;
  size_t j = startIndex + length - 1;

  //Loop while the start and end indicies are in different bytes
  while (i / 8 < j / 8) {
    //Reverse based on the byte with the least bits needing to be swapped
    size_t leftSeg  = 8 - i % 8; //Swappable bits in left array
    size_t rightSeg = j % 8 + 1; //Swappable bits in right array

    size_t minSeg = leftSeg <= rightSeg ? leftSeg : rightSeg; //Get the max # of bits we can swap this iteration

    byte_subset_reverse_swap(&(ba->buf[i/8]), &(ba->buf[j/8]), minSeg, i%8, j%8); //Perform in-place swap

    i += minSeg; //Advance the loop state variables, narrowing the remaining range to reverse
    j -= minSeg;
  }

  //Final single-byte reversal, only done if there are bytes left to reverse.
  if (i < j) {
    single_byte_subset_reverse(&(ba->buf[i/8]), j-i+1, i%8);
  }
}

/* Swap reversed subsets of bits in two different bytes; used to flip bits moving inward */
void byte_subset_reverse_swap(char *leftByte, char *rightByte, size_t length, size_t leftStart, size_t rightEnd) {
  char leftRot = bit_reverse_table[(unsigned)(unsigned char)*leftByte];
  char rightRot = bit_reverse_table[(unsigned)(unsigned char)*rightByte];

  //Store the new left value, as the old one needs to be referenced temporarily 
  char leftNew = (*leftByte & (0xFF - (one_mask(length) << leftStart))) |
		   (bit_range_extract(7 - rightEnd, length, rightRot) << leftStart); 

  //Appears to work so far...
  *rightByte = (*rightByte & (0xFF - (one_mask(length) << (rightEnd - length + 1)))) |
	           (bit_range_extract(8 - leftStart - length, length, leftRot) << (rightEnd - length + 1)); 

  //Copy the temporary left value over the origional
  *leftByte = leftNew;
}

/* Reverse a subset of bits in a single byte, starting at leftStart with the given length */
void single_byte_subset_reverse(char *byteElem, size_t length, size_t leftStart) {
  //We use temporary holder variables for readibility, they are merged by the compiler

  //Get the reversed byte
  char byteRot = bit_reverse_table[(unsigned)(unsigned char)*byteElem];

  //Get the masked surrounding and masked+rotated internal components
  char surround = (*byteElem & (0xFF - (one_mask(length) << leftStart)));
  char internal = (bit_range_extract(8 - leftStart - length, length, byteRot) << leftStart );

  //Merge them together with an OR
  *byteElem = surround | internal; 
}
